The present invention relates to computer systems and more particularly to paged memory management for a run-time execution environment.
A dynamic run-time environment for a language such as JAVA(trademark) is responsible for managing memory for objects that are created and destroyed during the execution of a program. An object may be defined as a logically contiguous atomic unit of typed state of the program. Objects thus encapsulate data in particular regions of memory that are allocated and deallocated for the program by the dynamic run-time environment.
Differences between server environments make machine independence very difficult to achieve for portable run-time environments. For example, some operating systems, in practice if not by design, limit the guaranteed size of contiguous virtual memory to a xe2x80x9cpage,xe2x80x9d typically about two or four kilobytes in size, and prior paged memory systems simply failed when sufficient large blocks of virtual memory was not available. This page-size limitation is particularly common for allocating objects in shared memory for access by different processes.
If the run-time environment is adapted to allow objects to be allocated in a plurality of non-contiguous pages, however, then the overhead in calculating which parts of an object belong to which pages becomes a significant factor in system performance. For example, one way to determine which pages belong to an object is to maintain an ancillary data structure called a page map that lists a set of pages in a logical order. If a part of object at a given displacement cannot fit on a page based on the location of the beginning of the object in the page and the displacement into the object, the page map is consulted to determine the next logical page or pages for the part of the object that cannot fit on the first page.
When an object in a paged memory management system crosses a page boundary (referred herein to as a xe2x80x9cpaged objectxe2x80x9d), slot-access operations for the object need additional support from the run-time environment. A slot-access operation gets or sets a value of a xe2x80x9cslotxe2x80x9d in a object (i.e. a field or instance variable) at a known displacement from the virtual address of the beginning of the object. If the object is contiguous or fits on a single page, then the address of the slot can be determined simply by adding the displacement to the beginning of the object. For paged objects, on the other hand, this addition results in an invalid address when the displacement crosses one more page boundaries, because the page boundary may occur between any of the slots and vary from instance to instance.
Accordingly, a slot-access operation of a machine pointer to a paged object requires checking to see if adding the displacement crosses one or more page boundaries. When there is such an xe2x80x9cexcess displacement,xe2x80x9d the logical page number and page offset for the displacement address is calculated, and the address of the beginning of the page is fetched from the page map and dereferenced with the page offset. This calculation is complicated when a certain amount of each page is reserved in a page header, for example, by the operating system or the run-time environment to store administrative information about the page. Conventionally, the page header is kept as small as practical because the page header represents overhead that is not available for storing objects of the program.
In accordance with one approach, the logical page number and the page offset are calculated by computing the integer quotient and remainder of the excess displacement with the effective size of the page. For example, if the page size is 4096 (212) and the page header size is 120, then the effective page size is 4096xe2x88x92120=3976. For an excess displacement of 5000, the calculated integer quotient is 5000%3976=1, and the calculated remainder is 5000% 3976=1024. Thus, the address of the slot is 1024 bytes past the header of the first page after the next page.
Micro-benchmarks on the Pentium(trademark) processor have determined that more than half of the time required to compute the slot address is spent performing the integer division and remainder calculations. Because slot-access calculations consume a significant portion of the run-time environment""s time budget for all operations (e.g. about 5%), overall system performance of the run-time environment can be improved by improving the performance of the slot-access computation.
Therefore, there is a need for improving the performance of a run-time environment operating with a paged memory management system. More specifically, a need exists for a fast method of computing the slot address of a paged object, particularly when the logical displacement of the slot results in an address on another page. There exists a need for avoiding integer division and remainder operations by the processor in slot-access calculations.
These and other needs are addressed by the present invention, in which the integer division and remainder operations are replaced by a fast division technique that counts the number page boundaries crossed by the logical displacement and adding back into the remainder the size of the page header for each page boundary crossings. Accordingly, it is possible to employ arithmetical-logical operations of shifting and masking, which are faster than most hardware implementations of integer division and modulus, respectively. In another aspect, the use of these operations is facilitated by requiring the page size and the size of the page header to be a power of two.
Accordingly, one aspect of the invention pertains to a computer-implemented method and a computer-readable medium bearing instructions for accessing a slot of an object allocated on more than one page, when the slot is logically located at an excess displacement from an end of the first page upon which the object is allocated. Each page has the same page size and a page header of the same size. In accordance with this methodology, the number of page boundaries crossed by the excess displacement is calculated, e.g. by shifting, to identify which one of the pages the slot is located upon. A page offset for an address of the slot is calculated by adding a remainder of the excess displacement modulo the page size, e.g. by masking, and the number of crossed page boundaries in units of the common page header size. Thus, the slot is accessed at the page offset from the beginning of the identified page.
Another aspect of the invention relates to a computer-implemented and a computer-readable medium bearing instructions for managing memory in a paged memory system. In this system, 2M bytes of memory is allocated for each page, and 2K is allocated for each page header by padding where necessary. Consequently, a slot of an object, when the slot is located at an excess displacement from the end of the first page for the object, is accessed by calculating a quotient and remainder of the excess displacement modulo 2Mxe2x88x922K. The quotient indicates the page containing the slot and the remainder indicates the logical offset on the page for the slot.
In one embodiment, the quotient and remainder of the excess displacement modulo 2Mxe2x88x922K is calculated by shifting the excess displacement by K bits to produce a first partial quotient; masking the excess displacement to retain the K least significant bits thereof to produce a first partial remainder; calculating a second partial quotient and a second partial remainder of the first partial quotient by 2Mxe2x88x92Kxe2x88x921; shifting the second partial remainder by K bits and adding a result thereof and the first partial remainder to produce the remainder; and establishing the second partial quotient as the quotient.
In another embodiment, the quotient and remainder of the excess displacement modulo 2Mxe2x88x922K is calculated by comparing the excess displacement and 2Mxe2x88x922K; if the excess displacement is less than 2Mxe2x88x922K, then establishing zero as the quotient and the excess displacement as the remainder; otherwise by establishing the excess displacement as a current value; calculating a first value as a quotient of the current value divided by 2M; calculating a second value as a remainder of the current value modulo 2M; adding the second value and a product of the first value and 2K to produce the current value; and establishing the current value as the remainder.
Still other objects and advantages of the present invention will become readily apparent from the following detailed description, simply by way of illustration of the best mode contemplated of carrying out the invention. As will be realized, the invention is capable of other and different embodiments, and its several details are capable of modifications in various obvious respects, all without departing from the invention. Accordingly, the drawing and description are to be regarded as illustrative in nature, and not as restrictive.